﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Xml.Serialization;
using System.IO;

namespace MyopicScheduler
{
    class Program
    {
        static void Main(string[] args)
        {
            //check that enough parameters are given
            if (args.Length < 4)
            {
       
                //Console.WriteLine("Error: Not enough parameters");
                return;
            }

            int windowSize = Convert.ToInt32(args[0]);
            int numBacktracks = Convert.ToInt32(args[1]);
            int weight = Convert.ToInt32(args[2]);
            String xmlFile = args[3];

            //check that file exists
            if (!File.Exists(xmlFile))
            {
                //Console.WriteLine("Error: File does not exist");
                return;
            }

            //set verbose mode
            bool verbose = false;
            if (args.Length > 4)
            {
                if (args[4].Equals("-v"))
                    verbose = true;
            }

            //open serialized simulation set
            XmlSerializer serial = new XmlSerializer(typeof(SimulationData));
            FileStream file = new FileStream(xmlFile, FileMode.Open);
            SimulationData data = (SimulationData)serial.Deserialize(file);

            Scheduler myopicScheduler = new Scheduler();

            int i = 0;
            int successCount = 0;
            foreach(TaskSet taskSet in data.TaskSets)
            {
                if(verbose)
                    Console.WriteLine("Scheduling TaskSet {0}", i);

                if (myopicScheduler.Schedule(taskSet, windowSize, weight, numBacktracks, verbose))
                {
                    successCount++;
                }

                i++;

                //wait to close console
                if(verbose)
                  Console.ReadKey();
            }

            //return successCount;
            Console.WriteLine("\n{0} tasksets out of {1} were sucessfully scheduled", successCount, i);
            if(verbose)
                Console.ReadKey();
        }
    }

    class Scheduler
    {
        public bool Schedule(TaskSet data, int windowSize, int weight, int numBacktracks, bool pVerbose)
        {
            int backtrack = 0;

            if (data.Tasks.Count == 0)
            {
                if(pVerbose)
                    Console.WriteLine("No Tasks to Schedule");
                return true;
            }

            //sort tasks by deadline
            data.Tasks.Sort(new TaskComparer());

            int i = 0;
            if (pVerbose)
            {
                foreach(Task t in data.Tasks)
                {
                    Console.WriteLine("Task {0} C: {1} R: {2} D: {3}", i, t.CompTime, t.ReadyTime, t.Deadline);
                    i++;
                }
                Console.ReadKey();
            }

            //create new tree
            List<TreeStep> SearchTree = new List<TreeStep>();
            TreeStep step = new TreeStep(data.NumResources, data.NumProcessors, windowSize, data.Tasks);
            SearchTree.Add(step);
            if (step.StronglyFeasible(weight) == false)
            {
                if(pVerbose)
                    Console.WriteLine("Schedule Failed: first step failed");

                return false;
            }
            WindowItem scheduledTask = step.ScheduleItem();

            while(step.QueueCount() > 1)
            {
                step = new TreeStep(SearchTree.Last<TreeStep>(), scheduledTask, windowSize, data.Tasks, pVerbose);
                SearchTree.Add(step);

                //check feasability
                while (step.StronglyFeasible(weight) == false)
                {
                    //perform backtrack
                    backtrack++;

                    if(pVerbose)
                        Console.WriteLine("Backtrack {0}", backtrack);

                    if (backtrack > numBacktracks)
                    {
                        if(pVerbose)
                            Console.WriteLine("Schedule Failed: backtracks exceeded");
                        return false;
                    }
                    
                    //remove unfeasible step
                    SearchTree.Remove(SearchTree.Last<TreeStep>());
                    //run out of steps
                    if (SearchTree.Count == 0)
                    {
                        if(pVerbose)
                            Console.WriteLine("Schedule Failed: ran out of steps");
                        return false;
                    }

                    //go back to previous step
                    step = SearchTree.Last<TreeStep>();

                    //if there is empty steps
                    while (step.EmptyWindow())
                    {
                        SearchTree.Remove(SearchTree.Last<TreeStep>());
                        //run out of steps
                        if (SearchTree.Count == 0)
                        {
                            if(pVerbose)
                                Console.WriteLine("Schedule Failed: ran out of steps");
                            return false;
                        }
                        step = SearchTree.Last<TreeStep>();
                    }
                }

                //retrieve scheduled task
                scheduledTask = step.ScheduleItem();
            }

            //add final step to tree
            step = new TreeStep(SearchTree.Last<TreeStep>(), scheduledTask, windowSize, data.Tasks, pVerbose);
            SearchTree.Add(step);

            return true;
        }
    }

    class TreeStep
    {
        private List<int> Processors;
        private List<Resource> Resources;
        private List<WindowItem> TaskQueue;
        private List<WindowItem> TaskWindow;
        private List<Task> TaskSet;

        //Initial constructor for a new tree
        public TreeStep(int numResources, int numProcessors, int k, List<Task> pTaskSet)
        {
            Resources = new List<Resource>();
            Processors = new List<int>();
            TaskQueue = new List<WindowItem>();
            TaskSet = pTaskSet;
            int i = 0;

            //initalize empty resources
            for (i = 0; i < numResources; i++)
            {
                Resource rtemp = new Resource();
                Resources.Add(rtemp);
            }

            //initialize empty processors
            for (i = 0; i < numProcessors; i++)
            {
                Processors.Add(0);
            }

            //initialize task queue
            i = 0;
            foreach (Task task in pTaskSet)
            {
                WindowItem wtemp = new WindowItem(i, 0, 0);
                TaskQueue.Add(wtemp);
                i++;
            }

            //initialize task window
            TaskWindow = TaskQueue.GetRange(0, k);
        }

        //Constructor
        //Increment values of the new step from the last step
        public TreeStep(TreeStep t, WindowItem ScheduledTask, int k, List<Task> pTaskSet, bool verbose)
        {
            Resources = new List<Resource>();
            Processors = new List<int>();
            TaskQueue = new List<WindowItem>();
            TaskSet = pTaskSet;

            //time when new task ends
            int endTime = ScheduledTask.EST + TaskSet[ScheduledTask.queueIndex].CompTime;

            //make copy of resources
            foreach (Resource r in t.Resources)
            {
                Resource newResource = new Resource(r.ExclusiveAvailTime, r.SharedAvailTime);
                Resources.Add(newResource);
            }

            //make copy of processors
            foreach (int p in t.Processors)
            {
                Processors.Add(p);
            }

            //update resources
            foreach(ResourceLock l in pTaskSet[ScheduledTask.queueIndex].ResourceLocks)
            {
                Resources[l.ResourceNum].ExclusiveAvailTime = Math.Max(endTime, Resources[l.ResourceNum].ExclusiveAvailTime);

                if (l.Type == ResourceLockType.Exclusive)
                {
                    Resources[l.ResourceNum].SharedAvailTime = Math.Max(endTime, Resources[l.ResourceNum].SharedAvailTime);
                }
            }

            WindowItem temp;
            foreach (WindowItem w in t.TaskQueue)
            {
                temp = new WindowItem(w.queueIndex, w.EST, w.H);
                this.TaskQueue.Add(temp);
            }

            //update processor
            int minIndex = Processors.IndexOf(Processors.Min());
            Processors[minIndex] = endTime;

            //remove scheduled task from queue
            this.TaskQueue.RemoveAt(t.TaskQueue.IndexOf(ScheduledTask));

            //set window
            TaskWindow = TaskQueue.GetRange(0, Math.Min(k, TaskQueue.Count));

            if(verbose)
            {
                Console.WriteLine("Task {0} scheduled on Proc {1} from {2} to {3}", ScheduledTask.queueIndex, minIndex, ScheduledTask.EST, endTime);
                foreach(Resource r in Resources)
                {
                    Console.WriteLine("{0}({1})", r.SharedAvailTime, r.ExclusiveAvailTime);
                }
            }
        }

        public int QueueCount()
        {
            return TaskQueue.Count;
        }

        //determine if window items are strongly feasible
        public bool StronglyFeasible(int weight)
        {
            foreach (WindowItem w in TaskWindow)
            {
                w.EST = EST(TaskSet[w.queueIndex]);
                w.H = HeuristicAlg(w.EST, weight, TaskSet[w.queueIndex].Deadline);
                if (Feasible(TaskSet[w.queueIndex], w.EST) == false)
                    return false;
            }

            return true;
        }

        public WindowItem ScheduleItem()
        {
            if (TaskWindow.Count == 0)
            {
                return null;
            }

            //Sort items by H in increasing order
            TaskWindow.Sort();
            WindowItem temp = TaskWindow.First<WindowItem>();
            //remove item for backtracking
            TaskWindow.Remove(temp);
            return temp;
        }

        public bool EmptyWindow()
        {
            return TaskWindow.Count == 0;
        }

        private bool Feasible(Task t, int EST)
        {
            return (EST + t.CompTime <= t.Deadline);
        }

        private int HeuristicAlg(int EST, int weight, int deadline)
        {
            return deadline + (EST * weight);
        }

        private int EST(Task t)
        {
            int maxResource = 0;
            int readyTime = t.ReadyTime;
            int minAvail = Processors.Min();

            if (t.ResourceLocks != null)
            {
                if(t.ResourceLocks.Count > 0)
                    maxResource = maxResourceAvailTime(t.ResourceLocks);
            }

            return Math.Max(Math.Max(maxResource, readyTime), minAvail);
        }

        private int maxResourceAvailTime(List<ResourceLock> locks)
        {
            int maxResourceAvailTime = 0;

            //max avail time for resources
            foreach (ResourceLock l in locks)
            {
                if (l.Type == ResourceLockType.Exclusive)
                {
                    if (Resources[l.ResourceNum].ExclusiveAvailTime > maxResourceAvailTime)
                        maxResourceAvailTime = Resources[l.ResourceNum].ExclusiveAvailTime;
                }
                else
                {
                    if (Resources[l.ResourceNum].SharedAvailTime > maxResourceAvailTime)
                        maxResourceAvailTime = Resources[l.ResourceNum].SharedAvailTime;
                }
            }

            return maxResourceAvailTime;
        }
    }

    class TaskComparer : IComparer<Task>
    {
        // sorts in descending order
        public int Compare(Task t1, Task t2)
        {

            if (t1.Deadline < t2.Deadline)
                return -1;

            if (t1.Deadline > t2.Deadline)
                return 1;

            // equal
            return 0;
        }
    }

    class WindowItem : IComparable<WindowItem>
    {
        public int queueIndex;
        public int EST;
        public int H;

        //sort by H value
        public int CompareTo(WindowItem w)
        {
            if (this.H < w.H)
            {
                return -1;
            }
            else if (this.H == w.H)
            {
                return 0;
            }
            else
            {
                return 1;
            }
        }

        //constructor
        public WindowItem(int pQueueIndex, int pEST, int pH)
        {
            this.queueIndex = pQueueIndex;
            this.EST = pEST;
            this.H = pH;
        }
    }

    class Resource
    {
        public int ExclusiveAvailTime;
        public int SharedAvailTime;

        public Resource()
        {
            this.ExclusiveAvailTime = 0;
            this.SharedAvailTime = 0;
        }

        public Resource(int pExclusiveAvailTime, int pSharedAvailTime)
        {
            this.ExclusiveAvailTime = pExclusiveAvailTime;
            this.SharedAvailTime = pSharedAvailTime;
        }
    }
}
